package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 22:41 2020/4/2
 * @Description 最小路径和
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
 */

public class LeetCode_64 {
    // 此题一种是暴力另外一种就是动态规划，贪心算法是不能保证结果是正确的
    // 为了节省空间可以直接在原数组上进行修改
    // 只能下右和下走，因此它的上一个值一定是从左边或者上边来的（最小值）
    // 1. 如果处于全边界就是自己  2.如果有左，但无上，那就是左值+当前值
    // 3. 如果有上但无左，那就是上值+当前值 4. 如果都有就选择最小值+当前值
    public int minPathSum(int[][] grid) {

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) {
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                } else {
                    grid[i][j] = Math.min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
                }
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

}
